/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package Controle;

import Entidades.Link;
import Entidades.LocalizadoraDeNos;
import Entidades.LocalizadoraLinks;
import Entidades.No;
import java.util.ArrayList;
import Limite.Apresentacao;

/**
 *
 * @author Ian Rocha
 */
public class Floyd {

    private int matrizD[][];
    private int matrizP[][];
    private ArrayList<No> nos = new ArrayList<No>();
    private ArrayList<Link> links = new ArrayList<Link>();
    private Apresentacao ap;

    public void executa(Apresentacao ap) {
        //Cria a matris de distancias com o tamanho referente a quantidade de nós
        this.ap = ap;
        nos = LocalizadoraDeNos.getLista();
        links = ControleLinks.getTodosLinks();

        matrizP = getMatrizP(nos, links);
        matrizD = getMatrizDistancia(nos, links);
//        for (int i = 0; i < nos.size(); i++) {
//            for (int j = 0; j < nos.size(); j++) {
//                System.out.println("[" + i + "][" + j + "](" + matrizP[i][j] + ")");
//            }
//        }

        executaFloyd();


    }

    private int[][] getMatrizDistancia(ArrayList<No> nos, ArrayList<Link> links) {
        matrizD = new int[nos.size()][nos.size()];

        for (int i = 0; i < nos.size(); i++) {
            for (int j = 0; j < nos.size(); j++) {
                Link l = ControleLinks.getLink(nos.get(i), nos.get(j), links);
                if (i == j) {
                    matrizD[i][j] = 0;
                } else if (l != null) {
                    matrizD[i][j] = (int) ControleNos.calculaDistancia(nos.get(i), nos.get(j));

                } else {
                    matrizD[i][j] = 100000;
                }
            }
        }
        return matrizD;
    }

    private int[][] getMatrizP(ArrayList<No> nos, ArrayList<Link> links) {
        matrizP = new int[nos.size()][nos.size()];
        for (int i = 0; i < nos.size(); i++) {
            for (int j = 0; j < nos.size(); j++) {
                if (i != j) {
                    matrizP[i][j] = i + 1;
                } else if (i == j) {
                    matrizP[i][j] = 0;
                }
            }
        }
        return matrizP;
    }

    private void executaFloyd() {
        ArrayList<int[][]> mDs = new ArrayList<int[][]>();
        ArrayList<int[][]> mPs = new ArrayList<int[][]>();
        int mD[][] = null;
        int mP[][] = null;
        mDs.add(matrizD);
        mPs.add(matrizP);

        for (int k = 1; k < nos.size(); k++) {
            int matrizD_2[][] = new int[nos.size()][nos.size()];
            int matrizP_2[][] = new int[nos.size()][nos.size()];

            for (int i = 0; i < nos.size(); i++) {
                for (int j = 0; j < nos.size(); j++) {

//                    if (k == 0) {
//                        //se for a primeira vez, ele pega o valor da matriz distancia
//                        mD = matrizD;
//                        mP = matrizP;
//                    } else { // se não ele pega o valor da matriz distancia anterior
                    mD = mDs.get(k - 1);
                    mP = mPs.get(k - 1);
//                    }
                    //VERIFICAR K ANTERIORES
                    matrizD_2[i][j] = Math.min(mD[i][j], (mD[i][k] + mD[k][j]));
                }
            }
            mDs.add(matrizD_2);
//            System.out.println("MDS: " + mDs);
            for (int i = 0; i < nos.size(); i++) {
                for (int j = 0; j < nos.size(); j++) {
                    System.out.println(matrizD_2[i][j] + "__" + mD[i][j]);

                    if (matrizD_2[i][j] != mD[i][j]) {
                        matrizP_2[i][j] = mP[k][j];
                    } else {
                        matrizP_2[i][j] = mP[i][j];
                    }
                }
            }
            mPs.add(matrizP_2);
//            System.out.println("MPS: " + mPs);
//            for (int i = 0; i < nos.size(); i++) {
//                for (int j = 0; j < nos.size(); j++) {
//                    System.out.print("(" + matrizP_2[i][j] + ") ");
//                }
//                System.out.println("");
//            }
//            for (int i = 0; i < nos.size(); i++) {
//                for (int j = 0; j < nos.size(); j++) {
//                    System.out.print("(" + matrizD_2[i][j] + ") ");
//                }
//                System.out.println("");
//            }
//            System.out.println("_________________________________________");
        }

        int origem = ap.jcbox_origem.getSelectedIndex() + 1;
        int destino = ap.jcbox_destino.getSelectedIndex() + 1;

        mP = mPs.get(mPs.size() - 1);
        boolean fim = false;
        ArrayList<Integer> resultNos = new ArrayList();
        resultNos.add(destino);

        do {
            if(origem==destino){
                break;
            }
            int next = mP[origem - 1][resultNos.get(resultNos.size() - 1) - 1];
            resultNos.add(next);
            if (next == origem) {
                fim = true;
            }
        } while (fim == false);

        ap.reset();
        for (int i = 0; i < resultNos.size()-1; i++) {
            ap.marcaCaminho(resultNos.get(i),resultNos.get(i+1));         
        }
        ap.atualiza();

    }
}
